[[2023年10月24日总结]] 此日做的题目。

CF1836A

link

此题比较容易，筒排以后验证一下是不是单调不增的就行。

CF1836B

link

特判一下答案是的情况，发现答案只和每个人分配的模的余数有关，并且余数之和同余为0。并且还可以发现要额外补充的钱都可以用节省的前来补上，因此只需要考虑将每个人都放满，然后计算模多出来的减掉就可以。 #数论

CF1836C/CF1835A

link

这道题我们首先会发现字典序和没有关系，因为，相同的话肯定相同，前两个不同肯定不同，所以字典序是由，决定的。那么就必要容易想了。我们先判断表达式是否有解，然后枚举，接着很容易就能把的范围算出来，最后就能根据算出答案对应的，然后就能求出式子了。而且会发现超过3位的测试点不超过5个，所以显然能够在规定的时间内通过。

CF1836D/CF1835B

link

这道题也是有一点难度的。最开始我是离散化了，后来发现这样反而更麻烦，只用排序就行。直观上看答案只用去找每个人前后两个以内的就行，因为此时能选择的范围的左右端点可能会发生一格的变化。

[[2023年10月26日总结]] 的题目。

CF1887A2

Dances (Hard Version)

题目大意。一个长为 n - 1 的 a 数组和长为 n 的 b 数组，枚举一个加入 a 的数从 1 到 m，然后求最大的 k 使得一个 a 的子序列和 b 的子序列一一对应时 a 都小于 b 的 k 的和。（我在说啥？你们还是去看题面吧）。会发现排序后 a 的前几位和 b 的后几位匹配。先二分求出不加入的一个最长的 l，容易发现小于一个数时会是 l + 1，大于后会是 l。那么就将 a 的前 l 位放在 b 的前 l + 1 位开始，一定会有一位开始不满足条件，那么这个地方的 b 值就是临界点。代码：link

CF1887B

Time Travel

虽然写起来不是很难，但是想还是有一点难度的。我最开始想的是分层图，但是会发现同一个时间可能会出现多次，如果暴力 bfs 或 转移会发现如果有一个时间有左右的边而这个时间反复出现就会爆炸。接着我们发现可以在一个地方停留。因此，我们想出了正解。直接把所有边都存在一个点中，我们 dijkstra，到一个点后考虑转移到另一个点。会发现要等到那条边出现的时间的时间才行。因此选择用主席树维护后缀各个时间出现的最早时间。然后就行了。注意细节，最后需要减一，因为到达后不需要再旅行了。时间复杂度差不多两个 log。代码很好写。代码：link 。 #图论

2023年11月2日更新。11月的第一场 vp。

[[2023年11月2日总结]] 这一天的题目！

link 这是链接。

话说我换这么多行干啥（有毛病）。做了 3 道题。有一个 B1 和 B2。emm，我直接做的 B2，所以时间有点长……。请 严格弱于我的 同学们不要学习这种 自以为是 过于自信的 技巧 侥幸心理。

所以还是 B1、B2 就一起讲了。B1 应该也不是特别难。哦对，这一天总结我不是在学校里写的，所以……比较简略，请见谅（废话比题解还多，什么鬼）。

CF1827A

这道题很简单，直接求比每一个 b 大的 a 的值有多少个再减去比这个数大的 b 值有多少个乘起来就行，很好证明。

CF1827B2

B1 的话请大家自己去思考了。这里我们会发现，对于一个串，它的代价是什么？我们首先可以发现它可以分成几段，就是长度减去段数。我们直接去找子串会发现很麻烦，于是我们就去找每一位的贡献，总的减去即可。现在我们需要确定一个段的贡献由哪一位决定？我最开始找的是每一段的第一个，后来发现很麻烦，还不能过 3e5 的点。于是我转换思路。就想每一段最小的那个。然后我们记录前面最近比它小的位置 l，和后面第一个比它小的位置 r（如果没有就是0和 n + 1），那么我们会发现这个子串的右端点不可能是 r，否则 r 就要到前面来，这个 i 位就不会最小了。那么左端点呢？我们会发现就是 l 左侧第一个大于 i 位的点 j 的右边开始。为什么呢？比较容易证明 j 的右边一定是可行的。那么 j 为什么不行？因为 j 位的值比 i 位的大，那么第一段就包含了
j 到 i 的所有数，最小的也不是 i。所以这样最后乘起来就行。不懂可以看代码：link 。 #字符串 #单调栈 #st表 #二分答案

[[2023年11月15日总结]] 的题目！

CF1868A

link 。

构造题，先特判的情况。然后会发现答案就是，从第 1 列（开始是 0 列）开始每一列放就行，然后发现每一行顺着放就行，多余的行移动一下位置放就行。提交记录 。

CF1868B1

link 。

先验证一下平均数。然后发现每个点会有出边和入边。刚好等于平均数的你可以发现可以插在任意位置，就可以不用管了。然后会发现出入边一定不等，验证一下每一种边的值对应的出入边的数量是否相等即可。提交记录 。

CF1868B2

link 。

会发现相对于前一道题，影响的只会有和平均数的差是2的幂可能会只有出入边。这种点就先假设度数只为1，然后记录一下这种每个值的个数。然后发现修改就对于下一个值加一，出边和入边反一下。然后枚举的时候发现不等尝试调整就行。提交记录 。

CF1868C

link

我的思路：首先对于一条链，枚举最大值，长度（点数）为，那么贡献就是。然后枚举最大值和长度，在枚举从 lca 两边往下的长度计算出有多少个长度为的链即可。两个。

P.S. 在写这里的时候我突然发现可以把长度为的链的个数预处理出来？惊呆我了，感觉突然降智！

更新：改了，然后发现循环里面还有个快速幂？！还是超时，决定优化掉快速幂。然后发现好像什么地方写寄了伤心。

更新：

我的代码跑得很快，139ms，全开 __int128 时间都才（你猜猜我为什么要全开 __int128，因为写的时候有个地方乘法溢出了），如果再减少一下取模的数量应该可以更快。时间复杂度。

具体怎么做呢？首先对于一条链，枚举最大值，长度（点数）为，那么贡献就是。然后枚举最大值和长度。我们容易发现链的不同长度数量是的，我们要求得每种长度的链的数量，然后和上面的贡献乘起来求和就行。那么我们怎么去求数量呢？我们考虑枚举一条链，从 lca 往两个儿子两边的长度是多少，会发现对于上面几层，对应的都是满二叉树，直接计算，需要特别计算的就是二叉树最下面一层的，特殊处理一下就可以。具体实现请看代码，要预处理一下幂。提交记录

CF708E

[[总结/2023年11月29日模拟赛|2023年11月29日模拟赛]] 的考试题 T2。

很容易想到的方法。然后前缀和一下，就变成了。考虑状态之搞一个端点，对另外一个求和，另外还能发现左右是对称的，再前缀和一次就完了。[[dp]]

CF1556H

DIY Tree

来自 [[2023年12月9日模拟赛]] 的 T4 的知识点 #拟阵 的习题。

简而言之，就是转化成了最小生成树和控制度数的两个拟阵求交。但是会发现直接搞度数这就不是个拟阵啊！那还交个毛，我们发现，造成这一切的主要都是前 k 个点内部连边会少 2 个度数，外面的是 0 或 1。于是我们暴力枚举 k 个点以内的连边情况就行。

注意：最后求到的最大独立集要判断大小！因为有可能不是一个生成树！